package leetcode_700;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import helpclass.TreeNode;

/**
 *@author 周杨
 *FindDuplicateSubtrees_652 寻找一棵二叉树中重复的子树
 *describe:用map保留遍历过的后序遍历 AC 47%
 *2018年9月27日 下午1:31:16
 */
public class FindDuplicateSubtrees_652 {
	 Map<String,TreeNode>hash;
		List<TreeNode> res;
		Set<String> set;
		public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
			this.hash=new HashMap<String,TreeNode>();
			this.res=new ArrayList<TreeNode>();
			this.set=new HashSet<String>();
			if(root==null)
				return this.res;
			help(root);
			for(String str:set) {
				res.add(hash.get(str));
			}
			return this.res;
	    }
		
		public String help(TreeNode root) {
			if(root==null)
				return "N";
			String now=help(root.left)+help(root.right)+root.val;
			if(hash.containsKey(now)) {
				set.add(now);
			}
			else {
				hash.put(now, root);
			}
			return now;
		}
}
